home *** CD-ROM | disk | FTP | other *** search
/ BBS in a Box 5 / BBS in a Box -Volume V (BBS in a Box) (April 1992).iso / Files / Prog / M / Mac gperf 1.9.cpt / Mac gperf 1.9 / src / perfect.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-03-11  |  12.0 KB  |  405 lines  |  [TEXT/KAHL]
  1. /* Provides high-level routines to manipulate the keywork list 
  2.    structures the code generation output.
  3.    Copyright (C) 1989 Free Software Foundation, Inc.
  4.    written by Douglas C. Schmidt (schmidt@ics.uci.edu)
  5.  
  6. This file is part of GNU GPERF.
  7.  
  8. GNU GPERF is free software; you can redistribute it and/or modify
  9. it under the terms of the GNU General Public License as published by
  10. the Free Software Foundation; either version 1, or (at your option)
  11. any later version.
  12.  
  13. GNU GPERF is distributed in the hope that it will be useful,
  14. but WITHOUT ANY WARRANTY; without even the implied warranty of
  15. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16. GNU General Public License for more details.
  17.  
  18. You should have received a copy of the GNU General Public License
  19. along with GNU GPERF; see the file COPYING.  If not, write to
  20. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  21.  
  22. #include <stdio.h>
  23. #include <assert.h>
  24. #include <time.h>
  25. #include <stdlib.h>
  26. #include <ctype.h>
  27.  
  28. #include "gperf.h"
  29. #include "xmalloc.h"
  30. #include "options.h"
  31. #include "stderr.h"
  32. #include "keylist.h"
  33.  
  34. #include "perfect.h"
  35.  
  36. int        occurrences[ ALPHABET_SIZE ]; /* Counts occurrences of each key set character. */
  37. int        asso_values[ ALPHABET_SIZE ]; /* Value associated with each character. */
  38.  
  39.     /* Locally visible PERFECT object. */
  40.  
  41. PERFECT        perfect;
  42.  
  43. /* Efficiently returns the least power of two greater than or equal to X! */
  44.  
  45. #define POW(X) ((!X)?1:(X-=1,X|=X>>1,X|=X>>2,X|=X>>4,X|=X>>8,X|=X>>16,(++X)))
  46.  
  47.  
  48. /*******************************************************************************\
  49. *                              Prototypes                                        *
  50. \*******************************************************************************/
  51.  
  52. static int        merge_sets( char * set_1, char * set_2, char * set_3 );
  53. static void        sort_set( char * union_set, int len );
  54. static int        hash( LIST_NODE * key_node );
  55. static bool        affects_prev( char c, LIST_NODE * curr );
  56. static void        change( LIST_NODE * prior, LIST_NODE * curr );
  57.  
  58.  
  59.     /***********************************************************************\
  60.     *                                                                        *
  61.     * name:        perfect_init                                                *
  62.     *                                                                        *
  63.     * descr:    Reads input keys, possibly applies the re-ordering             *
  64.     *            heuristic, sets the maximum associated value size             *
  65.     *            (rounded up to the nearest power of 2), may initialize         *
  66.     *            the associated values array, and determines the maximum     *
  67.     *            hash table size.                                            *
  68.     *                                                                        *
  69.     * notes:    Using the random numbers is often helpful, although not     *
  70.     *            as determinstic of course.                                    *
  71.     *                                                                        *
  72.     \***********************************************************************/
  73.  
  74. void perfect_init()
  75. {
  76.     int        asso_value_max;
  77.     int        len;
  78.     int        keylen;
  79.  
  80.     perfect.best_char_choice = 0;
  81.     perfect.best_asso_value = 0;
  82.  
  83.         /*
  84.         **    Read keys from file. If the sort option was enabled,
  85.         **    sort them after reading.
  86.         */
  87.  
  88.     read_keys();
  89.  
  90.     if ( OPTION_ENABLED( option, ORDER ) )
  91.         reorder();
  92.  
  93.         /*
  94.         **    Set up max
  95.         */
  96.     
  97.     asso_value_max    = GET_ASSO_MAX( option );
  98.     len                = length();
  99.  
  100.     asso_value_max = ( asso_value_max ? asso_value_max * len : len );
  101.     SET_ASSO_MAX( option, POW (asso_value_max) );
  102.  
  103.         /*
  104.         **    If the random option was enabled, init the associated
  105.         **    values array to random values scattered in the range
  106.         **    0..asso_value_max
  107.         */
  108.     
  109.     if ( OPTION_ENABLED( option, RANDOM ) )
  110.     {
  111.         int i;
  112.  
  113.         srand( time( NULL ) );
  114.       
  115.         for ( i = 0; i < ALPHABET_SIZE; i++ )
  116.             asso_values[i] = ( rand() & asso_value_max - 1 );
  117.     }
  118.     else
  119.     {
  120.         int asso_value = INITIAL_VALUE( option );
  121.  
  122.         if ( asso_value )           /* Initialize array if user requests non-zero default. */
  123.         {
  124.             int        i;
  125.  
  126.             for ( i = ALPHABET_SIZE - 1; i >= 0; i-- )
  127.                 asso_values[i] = asso_value & GET_ASSO_MAX (option) - 1;
  128.         }
  129.     }
  130.  
  131.     keylen = OPTION_ENABLED( option, ALLCHARS ) ? max_key_length() : TOTAL_POSITIONS( option );
  132.     perfect.max_hash_value = max_key_length() + GET_ASSO_MAX( option ) * keylen;
  133.   
  134.     if ( OPTION_ENABLED( option, DEBUG ) )
  135.         fprintf( stderr, "number of keys = %d\nmaximum associated value is %d\n"
  136.                          "maximum size of hash table is %d\n",
  137.                          len, asso_value_max, perfect.max_hash_value );
  138. }
  139.  
  140.  
  141.     /***********************************************************************\
  142.     *                                                                        *
  143.     * name:        merge_sets                                                    *
  144.     *                                                                        *
  145.     * descr:    Merge two disjoint hash key sets to form the ordered         *
  146.     *            union of the sets. Precondition: both set_1 and set_2         *
  147.     *            must be ordered. Returns the length of the combined set.    *
  148.     *                                                                        *
  149.     \***********************************************************************/
  150.  
  151. static int merge_sets( char * set_1, char * set_2, char * set_3 )
  152. {
  153.   char *base = set_3;
  154.   
  155.   while (*set_1 && *set_2)
  156.     if (*set_1 == *set_2)
  157.       *set_3++ = *set_1++, set_2++; 
  158.     else
  159.       *set_3++ = *set_1 < *set_2 ? *set_1++ : *set_2++;
  160.   
  161.   while (*set_1)
  162.     *set_3++ = *set_1++; 
  163.   
  164.   while (*set_2)
  165.     *set_3++ = *set_2++; 
  166.   
  167.   *set_3 = '\0';
  168.   return set_3 - base;
  169. }
  170.  
  171. /* Sort the UNION_SET in increasing frequency of occurrence.
  172.    This speeds up later processing since we may assume the resulting
  173.    set (Set_3, in this case), is ordered. Uses insertion sort, since
  174.    the UNION_SET is typically short. */
  175.   
  176. static void sort_set( char * union_set, int len )
  177. {
  178.   int i, j;
  179.   
  180.   for (i = 0, j = len - 1; i < j; i++)
  181.     {
  182.       char curr, tmp;
  183.  
  184.       for (curr = i+1, tmp = union_set[curr]; 
  185.            curr>0 && occurrences[tmp] < occurrences[union_set[curr-1]]; 
  186.            curr--)
  187.         union_set[curr] = union_set[curr - 1];
  188.       
  189.       union_set[curr] = tmp;
  190.     }
  191. }
  192.  
  193.  
  194.     /***********************************************************************\
  195.     *                                                                        *
  196.     * name:        hash                                                        *
  197.     *                                                                        *
  198.     * descr:    Generate a key set's hash value.                            *
  199.     *                                                                        *
  200.     \***********************************************************************/
  201.  
  202. static int hash( LIST_NODE * key_node )
  203. {                             
  204.     int            sum = OPTION_ENABLED( option, NOLENGTH ) ? 0 : key_node->length;
  205.     char *        ptr;
  206.  
  207.     for ( ptr = key_node->key_set; *ptr; ptr++ )
  208.         sum += asso_values[ *ptr ];
  209.  
  210.     return key_node->hash_value = sum;
  211. }
  212.  
  213.     /***********************************************************************\
  214.     *                                                                        *
  215.     * name:        affects_prev                                                *
  216.     *                                                                        *
  217.     * descr:    Find out how character value change affects successfully    *
  218.     *            hashed items. Returns FALSE if no other hash values are     *
  219.     *            affected, else returns TRUE.                                *
  220.     *                                                                        *
  221.     * notes:    Because option.get_asso_max is a power of 2 we can             *
  222.     *            guarantee that all legal asso_values are visited without    *
  223.     *            repetition, since option.get_jump was forced to be an         *
  224.     *            odd value.                                                    *
  225.     *                                                                        *
  226.     \***********************************************************************/
  227.  
  228. static bool affects_prev( char c, LIST_NODE * curr )
  229. {
  230.     int        original_char = asso_values[c];
  231.     int        i = ! OPTION_ENABLED( option, FAST ) ? GET_ASSO_MAX( option ) :
  232.             GET_ITERATIONS( option ) == 0 ? key_list.list_len : GET_ITERATIONS( option );
  233.  
  234.         /* Try all legal asso_values. */
  235.  
  236.     while ( --i >= 0 )
  237.     { 
  238.         int                number_of_hits = 0;
  239.         LIST_NODE *        ptr;
  240.  
  241.         asso_values[c] = asso_values[c] + (OPTION_ENABLED (option, FAST) ? rand() : GET_JUMP (option))
  242.                 & GET_ASSO_MAX (option) - 1;
  243.         bool_array_reset();       /* Ullman's array is a win, O(1) intialization time! */
  244.  
  245.         for ( ptr = key_list.head; ; ptr = ptr->next )
  246.         {
  247.             if ( lookup( hash( ptr ) ) && ++number_of_hits >= perfect.fewest_hits )
  248.                 goto bottom_of_main_loop;
  249.             if ( ptr == curr )
  250.                 break;
  251.         }    
  252.  
  253.         perfect.best_asso_value  = asso_values[ perfect.best_char_choice = c ];
  254.         if ( ( perfect.fewest_hits = number_of_hits ) == 0 )    /* Use if 0 hits for this value. */
  255.             return FALSE;        
  256.       
  257.     bottom_of_main_loop:
  258.         ;
  259.     }
  260.  
  261.     asso_values[ c ] = original_char;    /* Restore original values, no more tries. */
  262.     return TRUE;                        /* If we're this far it's time to try the next character.... */
  263. }
  264.  
  265.  
  266.     /***********************************************************************\
  267.     *                                                                        *
  268.     * name:        change                                                        *
  269.     *                                                                        *
  270.     * descr:    Change a character value, try least-used characters         *
  271.     *            first.                                                        *
  272.     *                                                                        *
  273.     \***********************************************************************/
  274.  
  275. static void change( LIST_NODE * prior, LIST_NODE * curr )
  276. {
  277.     char *        union_set = (char *) xmalloc( 2 * TOTAL_POSITIONS (option) + 1 );
  278.     int            i = 1;
  279.     char *        temp;
  280.     LIST_NODE *    ptr;
  281.  
  282.     if ( OPTION_ENABLED( option, DEBUG ) )        /* Very useful for debugging. */
  283.         fprintf (stderr, "collision, prior->key = %s, curr->key = %s, hash_value = %d\n",
  284.                     prior->key, curr->key, curr->hash_value);
  285.  
  286.     sort_set (union_set, merge_sets (prior->uniq_set, curr->uniq_set, union_set));
  287.  
  288.         /* Try changing some values, if change doesn't alter other values continue normal action. */
  289.  
  290.     perfect.fewest_hits = length();
  291.  
  292.     for ( temp = union_set; *temp; temp++ )
  293.         if ( !affects_prev( *temp, curr ) )
  294.             return;        /* Good, doesn't affect previous hash values, we'll take it. */
  295.   
  296.     asso_values[ perfect.best_char_choice ] = perfect.best_asso_value; /* If none work take best value. */
  297.   
  298.     for ( ptr = key_list.head; ; ptr = ptr->next, i++ )
  299.     {
  300.         hash( ptr );
  301.         if ( ptr == curr )
  302.             break;
  303.     }           
  304.  
  305.     if ( OPTION_ENABLED( option, DEBUG ) )
  306.         fprintf( stderr, "changes on %d hash values still produce duplicates, continuing...\n", i );
  307.  
  308.     free( union_set );
  309. }
  310.  
  311.     /***********************************************************************\
  312.     *                                                                        *
  313.     * name:        perfect_generate                                            *
  314.     *                                                                        *
  315.     * descr:    Initializes the Ullman_Array, and then attemps to find a    *
  316.     *            perfect function that will hash all the key words             *
  317.     *            without getting any duplications. This is made much         *
  318.     *            easier since we aren't attempting to generate *minimum*     *
  319.     *            functions, only perfect ones.                                *
  320.     *                                                                        *
  321.     * notes:    If we can't generate a perfect function in one pass         *
  322.     *            *and* the user hasn't enabled the DUP option, we'll         *
  323.     *            inform the user to try the randomization option -D, or         *
  324.     *            choose alternative key positions. The alternatives             *
  325.     *            (back-tracking) are too time-consuming, exponential in         *
  326.     *            the number of keys.                                            *
  327.     *                                                                        *
  328.     \***********************************************************************/
  329.  
  330. int perfect_generate()
  331. {
  332.     LIST_NODE *        curr;
  333.   
  334.     bool_array_init( perfect.max_hash_value );
  335.     hash( key_list.head );
  336.     
  337.     for ( curr = key_list.head->next; curr; curr = curr->next)
  338.     {
  339.         LIST_NODE *        ptr;
  340.  
  341.         hash( curr );
  342.       
  343.         for ( ptr = key_list.head; ptr != curr; ptr = ptr->next )
  344.             if ( ptr->hash_value == curr->hash_value )
  345.             {
  346.                 change (ptr, curr);
  347.                 break;
  348.             }
  349.     } 
  350.  
  351.         /**
  352.         ***  Make one final check, just to make sure nothing
  353.         ***  weird happened...
  354.         **/
  355.  
  356.     bool_array_reset();
  357.  
  358.     for ( curr = key_list.head; curr; curr = curr->next )
  359.         if ( lookup( hash( curr ) ) )
  360.         {
  361.             if ( OPTION_ENABLED( option, DUP ) ) /* We'll try to deal with this later..... */
  362.                 break;
  363.             else    /* Yow, big problems.  we're outta here! */
  364.             { 
  365.                 report_error(    "\nInternal error, duplicate value %d:\n"
  366.                                 "try options -D or -r, or use new key positions.\n\n", 
  367.                                     hash (curr));
  368.                 return 1;
  369.             }
  370.         }
  371.  
  372.     /*    First sorts the key word list by hash value, and the outputs the
  373.         list to the proper ostream. The generated hash table code is only 
  374.         output if the early stage of processing turned out O.K. */
  375.  
  376.     sort();
  377.     print_output();
  378.     return 0;
  379. }
  380.  
  381.     /***********************************************************************\
  382.     *                                                                        *
  383.     * name:        perfect_destroy                                                *
  384.     *                                                                        *
  385.     * descr:    Print out some diagnostics on completion.                    *
  386.     *                                                                        *
  387.     \***********************************************************************/
  388.  
  389. void perfect_destroy()
  390. {                             
  391.     if ( OPTION_ENABLED( option, DEBUG ) )
  392.     {
  393.         int        i;
  394.  
  395.         fprintf( stderr, "\ndumping occurrence and associated values tables\n" );
  396.  
  397.         for ( i = 0; i < ALPHABET_SIZE; i++ )
  398.             if ( occurrences[i] )
  399.                 fprintf( stderr, "asso_values[%c] = %3d, occurrences[%c] = %3d\n",
  400.                             i, asso_values[i], i, occurrences[i] );
  401.  
  402.         fprintf( stderr, "end table dumping\n" );
  403.     }
  404. }
  405.